#include <stdio.h>

/*

NOTE: 
The mergesort boils downs to this.. 
Given two sorted array's how do we merge this?

We need a new array to hold the result of merging
otherwise it is not possible to do it using array, 
so we may need a linked list

*/

void merge(int a[], int i, int j)
{
	int mid = (i+j)/2;
	int ai = i;
	int bi = mid+1;

	int newa[j-i+1], newai = 0;
	
	while(ai <= mid && bi <= j) {
		if (a[ai] > a[bi])
			newa[newai++] = a[bi++];
		else 			
			newa[newai++] = a[ai++];
	}

	while(ai <= mid) {
		newa[newai++] = a[ai++];
	}
				
	while(bi <= j) {
		newa[newai++] = a[bi++];
	}
	
	for (ai = 0; ai < (j-i+1) ; ai++)
		a[i+ai] = newa[ai];

}

void mergesort(int a[], int i, int j)
{
		int mid = (i+j) / 2;
		
		if (i >= j) return;
		
		mergesort(a, i, mid);
		mergesort(a, mid+1, j);
		merge(a, i, j);
		return;
}


int main()
{
//int a[] = { 1113,1140,1145,1149,1172,1176,1181,1199,1204,1208,1235,1240,1244,1267,1271,1276,1294,1299,1303,1330,1335,1339,1362,1366,1370,1389,1394,1397,1398,1425,1429,1434,1456,1457,1461,1465,1488,1492,1493,1519,1520,1524,1529,1551,1552,1556,1560,1578,1583,1587,1588,1614,1615,1619,1624,1646,1647,1651,1655,1673,1678,1682,1683,1709,1710,1714,1719,1741,1742,1746,1750,1773,1777,1778,1805,1809,1814,1836,1837,1840,1841,1845,1863,1868,1872,1873,1900,1904,1909,1931,1932,1936,1958,1963,1967,1968,1995,1999,2004,2026,2027,2031,2053,2058,2062,2063,2085,2089,2090,2094,2099,2121,2122,2125,2126,2153,2157,2158,2180,2184,2185,2189,2194,2216,2217,2221,2243,2248,2252,2275,2280,2284,2288,2311,2315,2343,2347,2370,2374,2379,2383,2406,2410,2433,2438,2442,2465,2469,2474,2478,2501,2505,2533,2537,2560,2564,2569,2573,2596,2600,2623,2628,2632,2655,2659,2664,2668,2691,2695,2718,2723,2727,2750,2754,2759,2763,2786,2790,2818,2822,2845,2849,2854,2858,2881,2885,2908,2913,2917,2940,2944,2949,2953,2976,2980,3008,3012,3035,3039,3044,3071,3075,3098,3103,3107,3130,3134,3138,3166,3169,3170,3193,3197,3201,3202,3225,3228,3229,3233,3260,3261,3264,3265,3288,3292,3296,3297,3319,3323,3324,3328,3355,3356,3360,3382,3383,3387,3391,3392,3414,3418,3419,3423,3450,3451,3455,3477,3478,3482,3486,3487,3509,3514,3518,3545,3546,3549,3550,3573,3577,3581,3582,3604,3608,3609,3613,3640,3641,3645,3668,3672,3676,3677,3699,3703,3704,3708,3735,3736,3739,3740,3762,3763,3767,3771,3772,3794,3798,3799,3803,3830,3831,3835,3857,3858,3862,3866,3867,3889,3893,3894,3898,3925,3926,3929,3930,3953,3957,3961,3962,3984,3989,3993,4020,4021,4025,4048,4052,4056,4079,4083,4088,4115,4119,4142,4147,4151,4174,4178,4183,4210,4214,4237,4242,4246,4269,4273,4278,4301,4305,4309,4332,4337,4341,4364,4368,4373,4396,4400,4404,4427,4432,4436,4459,4463,4468,4491,4495,4499,4522,4527,4531,4554,4558,4563,4586,4590,4594,4617,4622,4626,4649,4653,4658,4681,4685,4689,4712,4717,4721,4744,4748,4753,4776,4780,4784,4807,4812,4816,4839,4843,4848,4871,4875,4879,4902,4907,4911,4934,4938,4942,4966,4969,4970,4974,4997,5001,5005,5006,5028,5032,5033,5037,5060,5064,5065,5068,5069,5091,5092,5096,5100,5101,5123,5127,5128,5132,5155,5159,5160,5163,5164,5186,5187,5191,5195,5196,5218,5223,5227,5250,5254,5255,5258,5259,5281,5282,5286,5290,5291,5313,5318,5322,5345,5349,5350,5354,5376,5377,5381,5385,5386,5408,5409,5412,5413,5417,5440,5444,5445,5449,5471,5472,5476,5480,5481,5503,5504,5508,5512,5535,5539,5540,5543,5544,5566,5567,5571,5575,5576,5598,5599,5602,5603,5607,5630,5634,5635,5638,5639,5661,5662,5666,5670,5671,5693,5694,5698,5702,5725,5729,5730,5733,5734,5756,5757,5761,5765,5766,5788,5789,5792,5793,5797,5820,5824,5828,5852,5856,5860,5883,5887,5892,5915,5919,5923,5946,5951,5955,5978,5982,5987,6010,6014,6018,6041,6046,6050,6073,6077,6082,6105,6109,6113,6136,6141,6145,6168,6172,6177,6200,6204,6208,6231,6236,6240,6263,6267,6272,6295,6299,6303,6326,6331,6335,6358,6362,6367,6390,6394,6398,6421,6426,6430,6453,6457,6462,6485,6489,6493,6516,6521,6525,6548,6552,6557,6580,6584,6588,6611,6616,6620,6643,6647,6652,6675,6679,6683,6706,6711,6714,6715,6738,6742,6746,6769,6773,6774,6778,6801,6805,6809,6810,6832,6833,6836,6837,6841,6864,6868,6869,6873,6896,6900,6904,6905,6927,6928,6931,6932,6936,6959,6963,6964,6968,6990,6991,6995,6999,7000,7022,7023,7026,7027,7031,7054,7058,7059,7063,7085,7086,7090,7094,7095,7117,7118,7121,7122,7126,7149,7153,7154,7158,7180,7181,7185,7189,7190,7212,7213,7216,7217,7221,7244,7248,7249,7253,7275,7276,7280,7284,7285,7307,7308,7311,7312,7316,7339,7343,7344,7348,7370,7371,7375,7379,7380,7402,7403,7407,7411,7434,7438,7439,7443,7466,7470,7474,7475,7497,7498,7501,7502,7506,7529,7533,7534,7538,7560,7561,7565,7569,7592,7593,7597,7601,7624,7628,7632,7655,7660,7664,7687,7691,7696,7719,7723,7727,7750,7755,7759,7782,7786,7791,7814,7818,7822,7845,7850,7854,7877,7881,7886,7909,7913,7917,7940,7945,7949,7972,7976,7981,8004,8008,8012,8035,8040,8044,8067,8071,8076,8099,8103,8107,8130,8135,8139,8162,8166,8171,8194,8198,8202,8225,8230,8234,8257,8261,8266,8289,8293,8297,8320,8325,8329,8352,8356,8361,8384,8388,8392,8415,8420,8424,8447,8451,8455,8479,8483,8487,8510,8514,8518,8519,8541,8542,8545,8546,8550,8573,8577,8578,8582,8604,8605,8609,8614,8636,8637,8641,8645,8668,8672,8673,8677,8699,8700,8704,8709,8731,8732,8735,8736,8740,8758,8763,8767,8768,8772,8795,8799,8804,8826,8827,8830,8831,8835,8858,8862,8863,8867,8890,8894,8899,8921,8922,8926,8930,8953,8957,8958,8962,8984,8985,8989,8994,9016,9017,9020,9021,9025,9043,9048,9052,9053,9057,9079,9080,9084,9089,9111,9112,9115,9116,9120,9138,9143,9147,9148,9152,9174,9175,9179,9184,9206,9207,9210,9211,9215,9233,9238,9242,9243,9247,9269,9270,9274,9279,9301,9302,9306,9310,9333,9337,9338,9341,9364,9365,9369,9373,9396,9397,9400,9405,9428,9432,9436,9459,9464,9468,9491,9495,9500,9518,9523,9527,9531,9554,9559,9563,9586,9590,9595,9613,9618,9622,9626,9649,9654,9658,9681,9685,9690,9708,9713,9717,9744,9749,9753,9776,9780,9785,9808,9812,9839,9844,9848,9871,9875,9880,9898,9903,9907,9934,9939,9943,9966,9970,9975,9993,9998};
		//int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		int a[] = {9, 7, 2, 3, 5, 4, 1, 8, 6, 10};
		int i;

		mergesort(a, 0, 9);

		for (i = 0; i < 10; i++)
				printf ("%d ", a[i]);

		printf ("\n");

		return 0;
}
